//************************************************************
//    > File Name: climbing-stairs.cpp
//    > Author: davis
//    > Mail:  
//    > Created Time: 2017年03月21日 15:36:04
//***********************************************************
//lintcode #111
#include<bits/stdc++.h>
using namespace std;
int climbStairs(int n) {
	vector<int> steps(3, 0);
	steps[0] = 1;
	steps[1] = 1;
	for (int i = 2; i <= n; ++i) {
		steps[i % 3] = steps[(i - 1) % 3] + steps[(i - 2) % 3];
	}
	return steps[n % 3];
}
int climbStairs2(int n){
	int total;
	if(n==1 || n==2)
		total=n;
	else
		total=climbStairs(n-1)+climbStairs(n-2);
	return total;
}
int climbStairs3(int n){
	return (n==1 || n==2)?n:climbStairs3(n-1)+climbStairs3(n-2);
}
int climbStairs4(int n){
	int a=1,b=2,c;
	if(n==0) return 0;
	if(n==1 || n==2)
		return n;
	n -=2;
	while(n--){
		c=a+b;
		a=b;
		b=c;
	}
	return c;

}
int main(){
	cout<<"set a climbstairs number:";
	int n;
	cin>>n;
	int res=climbStairs4(n);
	cout<<res<<endl;
}

